package com.lims.algorithm.algset.dp;

/**
 * <功能简述>
 *
 * @author lims
 * @date 2020-05-26 15:02
 */

/**
 * 第21 题
 * 编程求解：
 * 输入两个整数n 和m，从数列1，2，3.......n 中随意取几个数,
 * 使其和等于m ,要求将其中所有的可能组合列出来
 */
public class FixedSum {

    public static void main(String[] args) {
        int m = 15;
        int n = 10;
        int[] marks = new int[n];
        FixedSum.find(n, m, marks);
    }

    public static void print(int[] marks) {
        for (int i = 0; i < marks.length; i++) {
            if (marks[i] == 1) {
                System.out.print(" " + (i + 1));
            }
        }
        System.out.println("");
    }

    public static void find(int n, int m, int[] marks) {
        //n和m的值不能小于1，否则从该次递归返回
        if (n < 1 || m < 1) {
            return;
        }
        //如果n大于m，则应该重置n为m，因为大于m的元素肯定不符合要求
        if (n > m) {
            n = m;
        }
        if (n == m) {
            //如果n==m，说明当前n元素是符合条件的
            marks[n - 1] = 1;
            //打印该组合
            print(marks);
            //打印完毕，将该元素n的状态恢复初始值
            marks[n - 1] = 0;
        }

        //先标记元素n，然后递归解决子问题f(n-1,m-n)
        //因为子问题f(n-1,m-n)所包含的符合条件的元素组合再加上元素n才能得到最终解，所以元素n标记为1
        marks[n - 1] = 1;
        find(n - 1, m - n, marks);

        //先标记元素n，然后递归解决子问题f(n-1,m)
        //此时元素n已经被排除在子问题f(n-1,m)之外了，所以将其标记为0
        marks[n - 1] = 0;
        find(n - 1, m, marks);
    }
}
